package com.ry.day1129;

import java.util.Arrays;

public class LC89 {

    static class Solution {
        /**
         * @param a:      An integer array
         * @param k:      A positive integer (k <= length(A))
         * @param target: An integer
         * @return: An integer
         */
        public int kSum(int[] a, int k, int target) {
            int n = a.length;
            Arrays.sort(a);
            int[][][] dp = new int[n+1][k+1][target+1];
            dp[0][0][0] =1;
            for (int i = 1; i <=n ; i++) {
                for (int j = 0; j <=k ; j++) {
                    for (int rest = 0; rest <=target ; rest++) {
                        dp[i][j][rest] = dp[i-1][j][rest];
                        if(j>=1 && rest>=a[i-1]) {
                            dp[i][j][rest] += dp[i-1][j-1][rest-a[i-1]];
                        }
                    }
                }
            }
            return dp[n][k][target];
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.kSum(new int[]{1, 2, 3, 4}, 2, 5));
    }
}
